Graph Theory Practice: SET G: (Plane graphs)

Prepared by:

Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk

1. For the graph G below:

a. Draw G - v for each vertex of G

b. Draw G - e for each edge of G

c. List the cut vertices of G if any.

d. List the bridges (cut edges) of G if any.

e. Draw the line graph of G. If the line graph of G is planar draw a plane embedding of the line graph.

2. Repeat the questions above for the graph G below:

Additionally:

f. Draw the medial graph of the graph above. How many vertices, edges and faces does this medial graph have?

g. Is the graph above 3-polytopal? If not, what is the minimum number edges that can be added to the graph to make it 3-polytopal?

h. Does the graph above have an Eulerian circuit? If so write one down. If not, give a reason, and find a Chinese Postman tour for this graph.